from typing import List

class Solution:
  def search(self, nums: List[int], target: int) -> int:
    if len(nums) == 0:
        return -1
    left = 0
    right = len(nums) - 1
    while left <= right:
        mid = (right + left) >> 1
        print(mid)
        if nums[mid] == target:
            return mid
        if nums[mid] > target:
            right = mid - 1
        if nums[mid] < target:
            left = mid + 1
    return -1


if __name__ == '__main__':
    s = Solution()
    print(s.search([-1,0,3,5,9,12], 9))